/*深度优先遍历三种方式*/
let deepTraversal1 = (node, nodeList = []) => {
  if (node !== null) {
    nodeList.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      deepTraversal1(children[i], nodeList)
    }
  }
  return nodeList
}

let deepTraversal2 = (node) => {
  let nodes = []
  if (node !== null) {
    nodes.push(node)
    let children = node.children
    for (let i = 0; i < children.length; i++) {
      nodes = nodes.concat(deepTraversal2(children[i]))
    }
  }
  return nodes
}

// 非递归
let deepTraversal3 = (node) => {
  let stack = []
  let nodes = []
  if (node) {
    // 推入当前处理的node
    stack.push(node)
    while (stack.length) {
      let item = stack.pop()
      let children = item.children
      nodes.push(item)
      // node = [] stack = [parent]
      // node = [parent] stack = [child3,child2,child1]
      // node = [parent, child1] stack = [child3,child2,child1-2,child1-1]
      // node = [parent, child1-1] stack = [child3,child2,child1-2]
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push(children[i])
      }
    }
  }
  return nodes
}

/**
 * 二叉树深度优先遍历
 * 先序遍历
 */
var tree = {
  value: "-",
  left: {
    value: '+',
    left: {
      value: 'a',
    },
    right: {
      value: '*',
      left: {
        value: 'b',
      },
      right: {
        value: 'c',
      }
    }
  },
  right: {
    value: '/',
    left: {
      value: 'd',
    },
    right: {
      value: 'e',
    }
  }
}
let result = [];
let dfs = function (node) {
  if (node) {
    result.push(node.value);
    dfs(node.left);
    dfs(node.right);
  }
}

dfs(tree);
console.log(result);
// ["-", "+", "a", "*", "b", "c", "/", "d", "e"]

// 非递归
let dfs2 = function (nodes) {
  let result = [];
  let stack = [];
  stack.push(nodes);
  while (stack.length) { // 等同于 while(stack.length !== 0) 直到栈中的数据为空
    let node = stack.pop(); // 取的是栈中最后一个j
    result.push(node.value);
    if (node.right) stack.push(node.right); // 先压入右子树
    if (node.left) stack.push(node.left); // 后压入左子树
  }
  return result;
}
dfs2(tree);